COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.every heading(,,{page})count page onecol select 7 verbatim
C00006 00003	.next page
C00011 00004	.next page
C00015 00005	.next page
C00019 00006	.next page
C00021 00007	.next page
C00026 00008	.next page
C00029 00009	.next page
C00032 00010	.next page
C00035 ENDMK
C⊗;
.every heading(,,{page});count page; onecol; select 7; verbatim
            AN EXTENSION TO THE PROGRAMMING LANGUAGE PASCAL,
                     TO SUPPORT SYSTEMS PROGRAMMING



                             John Hennessy
                             Forest Baskett

                           November 15, 1978






1.0 INTRODUCTION
	This report  defines  an  upward  compatible  extension  of  the
programming  language  Pascal. This extension is designed to support the
construction of large systems programs. A major attempt has been made to
keep  the goals of Pascal intact; in particular attention is directed at
simplicity, efficient runtime implementation and efficient  compilation,
language security, and compile-time type checking.

1.1 Report
	This report consists of four major sections. This first section,
introduces  the  language and two general extensions. The second section
defines a number of major language features and gives examples. The last
two  sections  are appendices: the first discusses a number of the major
design decisions behind the features of section2,  the  second  appendix
presents  some additional possible extensions which are interesting, but
are either still vague or do not seem necessary.

1.2 Defining Notation
	This  report  uses  the  BNF notation defined in the Pascal user
Manual. The existing BNF is not repeated but merely referred to (by  the
use of nonterminal symbols defined by that grammar).
	The  semantics  are  defined  informally;  a  formal   axiomatic
definition for the new features may be available later.

1.3 Restrictions
	This extension  is  completely  upward  compatible  with  the
Pascal  standard,  except for one point. This extension requires that
procedures which are parameters be fully typed, by defining the types
of  all  the  parameters  and  the  resultant  type  in the case of a
function. Thus the grammar for  a  parameter  which  is  a  procedure
becomes:

<formal parameter section> ::= <parameter group> 
			     | var <parameter group>
			     | <function heading> | <procedure heading>
.next page
1.4 General Extensions
	Two minor but general extensions to  the  language  are  defined
here.   The  first  is  the  relaxation  of the order of declaration for
constants,  types,  variables,   procedures   and   functions.     These
declaration sections are allowed to occur in any order and may occur any
number of times .  It is required that an identifier be declared  before
it  is  used.   Pointer  types are excluded from this rule. To eliminate
ambiguity, the following rule is introduced:
     If  a declaration refers to an identifier x, that identifier may
     not be declared later in the same scope, if it is declared in  a
     surrounding scope.

The new syntax for the declaration section becomes:
<block> ::= <label declaration part> <declarations> <statement part>
<declarations> ::= empty | <declaration> <declarations>
<declaration> ::= <constant definition part> | <type definition part>
		| <variable declaration part>
		| <procedure and function declaration part>

	The  second  extension  is  to  allow  the  utilization of an
include command.   This command with the syntax  include  <filename>,
will  cause the text in the file <filename> to be inserted in line in
the program.  The  command  may  appear  only  where  a  <block>,  or
<declarations>  could  appear.   Thus  this  construct can be used to
include sets of declarations and/or procedures or functions.


2.0 SPECIFIC EXTENDED LANGUAGE FEATURES

This  section  defines  a  number  of specific language extensions to
Pascal.

2.1 Type Constructors

<type constructor> ::= <type identifier> (<type specifier> )
<type identifier> ::= identifier
<type specifier> ::= <expression> 
		   |<type specifier> {, <type specifier>}
		   | ( <type specifier> )
		   | <type constructor>

	Consider  a type constructor of the form T ( <type specifier>
). The type name must not be a parameterized type. The  form  of  the
<type specifier> depends on the type name, T. The type T dictates the
form of the type specifier and the result of the type constructor, by
the following rules:
  1. Simple type or set type, then the  type  specifier  must  be  an
     expression  whose  value  is  implicitly coerceable to the type.
     The result is a value of type T equal to the value of  the  type
     specifier expression.
  2. Array type, then the type constructor must be a list of  values,
     whose types match the component type of the array. The result is
     a value of the array type  T,  with  the  components  being  the
     values  in  the type specifier. The matching of array components
     to values is  by  increasing  indices  matched  with  increasing
     positions in the list of values.
.next page
 3.  Record type, then the type specifier must be a list of values which
     match the fields of the record in order of  declaration  (including
     tag  field).   The  result  is  a  value of type T, with the record
     fields equal to the corresponding values from  the  type  specifier
     list.

	Type  constructors  may  appear  anywhere  a  variable  of   the
constructed  type could appear, except that they may not be assigned to.
Furthermore, if all the expressions in a type specifier are compile-time
constants  (see  next  section)  then  the result is a constant, and may
appear anywhere a constant might appear.
	In  the  type constructor for a string or a packed array of char
the abbreviation 'string of characters', may  be  used  for  a  list  of
character  constants;  the number of elements in the list must match the
length of the string of characters.

2.1.1 Examples
type	T = array [1..3] of integer;
	R = record
		field: integer;
		field2: T;
	end;

	S = set of 1..20;

const	OnetoThree = T (1,2,3);
var	x:T;
	i,j: integer;
	sset: S;
	rrecord: R;
type	Matrix = array [1..2,1..2] of real;
const	DiagMatrix = Matrix ((1,0),(0,1));

begin
	i := integer (4*5);
	sset := S([1,5..10,17]);
	rrecord := R(i,T(i,10,25));
	j := i + 45;
	x := T (4,5,i*j);
end.

2.2 Extended Constants

<constant definition> ::= <identifier> = <expression>

	The  concept  of a constant is extended to allow a broader class
of defining mechanisms. The first extension is to allow constants to  be
defined  by  any  compile-time  computable  expression.  A  compile-time
computable expression is defined to be an expression consisting  of  any
of   the   following:   manifest   constants,  defined  constants,  type
constructors, and the standard Pascal operators.   The  effect  of  this
extension  is  two  fold: constants may be compile-time expressions, and
constants may be defined of arbitrary types, including structured types.
.next page
2.3 Modules

<module> ::= module <module identifier> <file list>; <block> .
<file list> ::= <empty> 
	      | ( <file identifier> {, <file identifier>} )

	The module  facility  provides  the  ability  to  encapsulate
procedures, functions, data and types, as well as supporting separate
compilation. Modules may be separately compiled, and intermodule type
checking  will  be  done  as  part  of the linking process. Unless an
identifier is exported from a module, it is local to that module  and
can  not  be  used  from  other  modules.  Likewise  all  identifiers
referenced in a module must be either local or imported from  another
module.

2.2.1 Importing and exporting from modules

<declarations> ::= empty | import <declarations> end; <declarations>
	         | export <declarations> end; <declarations>
		 | <declaration> <declarations>
<procedure declaration> ::= <procedure heading> external
			  | <procedure heading> <block>
			  | <procedure heading> forward
<function declaration> ::= <function heading> external
			 | <function heading> <block>
			 | <function heading> forward

	Importing allows the use of variables,  types,  procedures,  and
functions  which are defined by other modules. Exporting allows a module
to make procedures, functions, variables and types  available  to  other
modules. All exported identifiers are treated as globals to all modules.
In order to reference an object declared by another module, it  must  be
exported  by  the declaring module and imported by the accessing module.
Since strong type checking is used, it is highly recommended that  types
be  exported and imported whenever a variable or procedure requires type
definitions. Import and export sections may not be nested.

2.2.2 An example - defining a stack module

module Stack;
(* defines an integer stack of size <= 100 *)

export
type	StackBounds = 0..100;
	Stk = record
		sp: StackBounds := StackBounds(0);
		intstack: array [StackBounds] of integer;
	end;

	procedure push (var s: stk; item: integer); forward;

	function pop (var s: stk): integer; forward;

	function empty (s: stk): boolean;
	begin
		if s.sp = 0 then empty := true else empty := false;
	end;
end;
.next page
procedure push (var s:stk; item: integer);
begin
	with s do if sp = 100 then ERROR
	else begin
		sp := succ (sp);
		intstack [sp] := item
	end
end; 	(* push *)

function pop (var s: stk): integer;
begin
	if empty (s) then ERROR
	else with s do begin
		pop := intstack[sp];
		sp := pred(sp);
	end;
end; 	(* Pop *)

end (* Stack *);


module UseStack;

import 
	type	StackBounds = 1..100;
		stk: record
			sp: StackBounds := StackBounds(0);
			intstack: array [StackBounds] of integer
		end;

	procedure push (s: stk; i: integer); external;
	function pop (s: stk): integer; external;
	function empty (s: stk): boolean; external;
end;


var s: stk;

    i: integer;

 .....
push (s,i);


end (* UseStack *);

(Note  that  this  function  is  really  more  suited  towards  a   data
abstraction  facility. The module facility is designed to support larger
functional units. The above example is only for illustration.)

.next page
2.4 Variable Initialization

<variable declaration> ::= <identifier> {,<identifier>} : <type> variable init>
<variable init> ::= <empty> | := <type constructor>
<record section> ::= <field identifier> {,<field identifier>} : <type> <variable init>
		     | <empty>
 
	Variable initialization is only allowed to variables   and fields of records at  the
global level of a module or a program. The type constructor must be a
constant. All variables in the identifier list  or field list are initialized to the
same value.

2.5 Explicit Type Coercion Functions
	Explicit type coercion functions which will convert the  type
of  an  expression from one type to another type whose representation
length is the same are provided. These coercion  functions  take  the
form  of  a  predefined  set  of functions; their implementation is a
compile-time operation of altering  the  type  (no  value  change  is
done).

2.6 Parametric Types
 
<type definition> ::= <identifier> = <type> 
		    | <parameterized type>
<parameterized type> ::= <identifier> <type parameter list> = <compound type>
<compound type> ::= <array type> | <record type>
<type parameter list> ::= ( <type parameter> {,<type parameter>} )
<type parameter> ::= <identifier> {,<identifier>} : <simple type>

 
	A   parameterized  type  is  a  type  definition  where  certain
identifiers, which would  normally  be  constants,  are  allowed  to  be
unspecified  parameters.  These  parameters  can only be used to specify
parameters in a component of the <compound type>  or  to  specify  array
bounds. A parameterized array type is an array type with the bounds left
specified as parameters.  The identifiers which are type parameters  are
local  to  the  type  definition.  Identifiers  within  the <array type>
specification which are also in the the type parameter list are bound to
those  type  parameters.  The  type parameters can only appear where the
array bounds  are  being  specified  (though  they  may  appear  in  the
specification of the bounds of a component type).   Also the bounds must
be specified as subranges, if the parameterized types are used.
	Parameterized types allow the  implementation  of  procedures
which  may  accept  a variety of different array sizes. Thus a formal
array parameter can  be  specified  to  be  a  parametric  type.  All
declarations  of  variables and constants must supply constant values
for the actual parameters.
	Since  a  parameterized  array could be a component of a record,
record types  are  also  allowed  to  have  parameters.  However,  these
parameters  can  only  be used to define the bounds of arrays within the
record.
	Two  predefined  functions upper and lower are provided. Both
functions take a single parameter of any array type, and  return  the
lower, or upper bound of that array.

.next page
2.6.1 Example
	In this example the stack module is  parameterized  to  allow
variable size stacks.

module Stack;

export 
	type stackbounds= 1..100;
	stk (size: Stackbounds) = record
		sp: stackbounds := stackbounds(0);
		intstack: array [1..size] of integer;
	end;
end;

procedure push (var s: stk; item: integer);
begin
	with s do if s.sp=upper(s.intstack) then ERROR
	...
	...
end; (* STACK *)



var 	s: stk(20);
	i: integer;
	...
	...

	push (s,i);

2.7 Strings
	A string facility which provides varying length strings  with
a maximum size limit on each string is included. The type string is a
parametric type where the parameter specifies the upper bound on that
string. The logical view on a string is defined by:
 
type string (n) = record
			length : 0..maxint;
			text : packed array [1..n] of char;
		 end
Note  that the string package is not really a language extension because
it consists of only a predefined type and a set of predefined procedures
operating on that type.
	Pascal string constants of the form 'characters' are  treated
as  string  constants where the actual parameter is the length of the
string.  Thus  the  constant  'ABC',  has  type  string(3),  and   is
considered an abbreviation for:
type string3 = string(3);

	string3(3,'ABC')
 
.next page
	The type string is  supported  by  a  variety  of  predefined
procedures for manipulating strings. These are briefly defined below:

 
procedure ASSIGN (source: string; var dest:string);
	dest <= source

function LENGTH (source: string): 0..maxint;
	LENGTH <= source.length

function POS (string1, string2: string): 0..maxint;
	POS <= starting position of string1 pattern in string2, else 0

procedure SUBSTR (source: string; var dest: string; sourcepos,
   destpos: 1..maxint; leng:0..maxint);

	dest.text [destpos..destpos+leng-1] <= source[sourcepos..sourcepos
	   +leng-1];
	dest.leng <= max (dest.length,destpos+length-1);

procedure CONCAT (source: string; var dest: string);
	dest.text [dest.length+1..dest.length+1+source.length] <= source.text
	dest.length <= dest.length + source.length;

function GETCHAR (source: string; sourcepos:1..maxint): char;
	GETCHAR <= source.text[sourcepos];

procedure PUTCHAR (source: char; var dest: string; destpos: 1..maxint);
	dest[destpos] := source;

The following string comparasion functions are supplied:
	STREQ,STRNE,STRLT,STRGT,STRGE,STRLE.
All  take  two  strings  as  operands and return true if the relation
holds.
 
	The  standard procedures READ and WRITE are adapted to handle
strings.

2.8 Loop-Exit Construct
 
<loop statement> ::=  loop <statement> {; <statement>} end
<exit statement> ::= exit
 
	The loop construct creates an potentially infinite loop, with no
explicit  termination  condition  (unlike  the while or for statements).
Within a loop statement one or  more  exit  statements  can  occur.  The
statement  exit  may  only  occur  within  the  static nesting of a loop
statement.  The semantics of the exit statement are to stop execution of
the  immediately  surrounding  loop statement and begin execution at the
statement following the end of the loop.
.next page
2.9 Packed Structures
	Provision  is  made  for  specifying  two  types  of  storage
packing.  If no packing is specified storage is allocated to optimize
access.  Packing  is  only   effective   on   arrays   and   records.
Specification  of  the  attribute packed will cause a decrease in the
use  of  storage.  The  compiler  will  allocate  packed   items   by
addressable  units.  Thus  each item in a packed array or record will
occupy the next largest addressable unit (byte, halfword, word), that
will accomodate its value range.
	The attribute bit packed can only be applied to record types.
It  will cause allocation of the fields of a record to be bit packed.
Thus the number of bits occupied by  a  field  will  be  the  minimum
number necessary to hold the range values of that field.
2.10 Storage Management
	The implementation will provide a standard procedure DISPOSE,
which takes a single parameter of any pointer type. The result of the
procedure is two-fold: the storage associated with the ptr  is  freed
(and  made  eligible for later allocation), and the pointer is set to
NIL.

2.11 Type Coercion
	Because the need to occasionally  violate  the  type  system  is
forseeable,  a  method  for  doing  this  in an explicit manner has been
included. A set of prdefined functions will provide coercion between any
two  length  compatable  types.  Note  that  the  coercion functions are
essentially a compile-time vehicle for altering a type.  They  will  not
require any runtime overhead.